#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""

def is_bipartite(edges, vertex_num):
    # 也可以使用dfs或者bfs来check
    set_a = set()
    set_b = set()
    set_all = set()     # set_a + set_b

    for end_a, end_b in edges:

        if end_a not in set_all and end_b not in set_all:
            # 都不在
            set_a.add(end_a)
            set_b.add(end_b)
            set_all.add(end_a)
            set_all.add(end_b)
            print('%s %s all new in ' % (end_a, end_b))
            continue

        elif end_a in set_all and end_b in set_all:
            # 两个节点分别在两个集合中
            if end_a in set_a and end_b in set_b:
                print('%s %s already in ' % (end_a, end_b))
                continue
            if end_a in set_b and end_b in set_a:
                print('%s %s already in ' % (end_a, end_b))
                continue

            print('%s %s conflict in ' % (end_a, end_b))

            return False

        else:
            # 只有一个节点在集合中
            # 先确定在集合中的节点, 用first.(不在集合中的节点用second表示)
            if end_a in set_all:
                first = end_a
                second = end_b
            else:
                first = end_b
                second = end_a

            # first must in all
            # second must not in
            if first in set_a:
                set_b.add(second)
            else:
                set_a.add(second)
            set_all.add(second)
            print('%s %s one new in ' % (end_a, end_b))

    # 结束后:节点个数要和set_all元素数量相同, 否则存在孤立节点.
    return len(set_all) == vertex_num


def test_ispartite():
    edges = [(1,2), (2, 3), (3, 4), (4, 1)]
    ret = is_bipartite(edges, 4)
    print(ret)

    ret = is_bipartite(edges, 5)
    print(ret)

def main():
    print("start main")
    test_ispartite()

if __name__ == "__main__":
    main()
